#include "ai.h"

QVector <Operation> MineSweeperAI::run(Block data[TABLE_ROWS_MAX][TABLE_COLS_MAX], int tableRows, int tableCols, int mineLast)
{
	srand(QDateTime::currentDateTime().toMSecsSinceEpoch());

	//	初始化游戏界面的数据

	this->tableRows = tableRows;
	this->tableCols = tableCols;
	this->uncoverCount = 0;
	this->mineLastCount = mineLast;
	this->unknownCount = 0;

	//	尝试执行简单的推理，寻找一定是地雷或一定不是地雷的位置

	clearData();
	getBlockData(data);
	getNumber();
	setMark();
	setUncover();

	if (uncoverCount == 0)
	{
		//	如果未能找到解决方案，则对每一个相互制约的部分枚举所有可能的解，并计算触雷的概率

		getLinkBlockData();
		removeInvalidLink();
		findAnswer();
		setResult();
	}
	if (uncoverCount == 0)
	{
		//	如果还是未能找到解决方案或不适合应用概率求解，则随机点开一个位置

		randClick();
	}
	return operationList;
}

void MineSweeperAI::leftClick(Point pos)
{
	//	返回左键点击该位置的操作

	operationList.append({ pos.x, pos.y, LEFT_CLICK });
	blockData[pos.x][pos.y].isCovered = false;
	uncoverCount += 1;
}

void MineSweeperAI::rightClick(Point pos)
{
	//	返回右键点击该位置的操作

	operationList.append({ pos.x, pos.y, RIGHT_CLICK });
	blockData[pos.x][pos.y].isMarked = true;
}

void MineSweeperAI::getBlockData(Block data[TABLE_ROWS_MAX][TABLE_COLS_MAX])
{
	//	获取传入的游戏界面信息并存储

	for (int x = 0; x < tableRows; x++)
	{
		for (int y = 0; y < tableCols; y++)
		{
			if (data[x][y].getIsCovered())
			{
				if (data[x][y].getIsMarked())
				{
					blockData[x][y].isMarked = true;
				}
				else { unknownCount += 1; }

				blockData[x][y].isCovered = true;
			}
			else if (data[x][y].getIsNumber())
			{
				blockData[x][y].number = data[x][y].getNumber();
			}
		}
	}
}

void MineSweeperAI::clearData()
{
	//	将已存储的游戏界面数据清空

	for (int x = 0; x < TABLE_ROWS_MAX; x++)
	{
		for (int y = 0; y < TABLE_COLS_MAX; y++)
		{
			blockData[x][y].number = 0;
			blockData[x][y].isFind = false;
			blockData[x][y].isMarked = false;
			blockData[x][y].isCovered = false;
		}
	}
	numberList.clear();
	linkList.clear();
	operationList.clear();
}

void MineSweeperAI::randClick()
{
	//	随机选择一个可以打开的位置并将其打开

	while (true)
	{
		int x = rand() % tableRows;
		int y = rand() % tableCols;

		if (blockData[x][y].isCovered && !blockData[x][y].isMarked)
		{
			leftClick({ x, y });
			break;
		}
	}
}

void MineSweeperAI::getNumber()
{
	//	获取界面中已被打开的数字存入数组中

	for (int x = 0; x < tableRows; x++)
	{
		for (int y = 0; y < tableCols; y++)
		{
			if (!blockData[x][y].isCovered && blockData[x][y].number != 0)
			{
				numberList.append({ x, y, blockData[x][y].number });
			}
		}
	}
}

void MineSweeperAI::setMark()
{
	//	根据数字标记确定为地雷的位置

	static QVector <Point> markList;

	for (int i = 0; i < numberList.size(); i++)
	{
		markList.clear();

		for (int sideX = -1; sideX <= 1; sideX++)
		{
			for (int sideY = -1; sideY <= 1; sideY++)
			{
				//	遍历该数字位置的四周

				int x = numberList[i].x + sideX;
				int y = numberList[i].y + sideY;

				if (x >= 0 && x < tableRows && y >= 0 && y < tableCols && blockData[x][y].isCovered)
				{
					//	如果在界面内且未被打开，则添加到标记列表

					markList.append({ x, y });
				}
			}
		}

		if (markList.size() == numberList[i].value)
		{
			//	如果标记列表的元素数量等于该位置数字的值，则说明四周所有未被打开的位置均为地雷，需要将其全部标记

			for (int j = 0; j < markList.size(); j++)
			{
				int x = markList[j].x;
				int y = markList[j].y;

				if (!blockData[x][y].isMarked)
				{
					rightClick({ x, y });
				}
			}
		}
	}
}

void MineSweeperAI::setUncover()
{
	//	根据数字和标记判断是否有可以安全打开的位置并将其打开

	static QVector <Point> uncoverList;

	for (int i = 0; i < numberList.size(); i++)
	{
		int markCount = 0;

		for (int sideX = -1; sideX <= 1; sideX++)
		{
			for (int sideY = -1; sideY <= 1; sideY++)
			{
				//	遍历该位置的四周

				int x = numberList[i].x + sideX;
				int y = numberList[i].y + sideY;

				if (x >= 0 && x < tableRows && y >= 0 && y < tableCols)
				{
					if (blockData[x][y].isMarked)
					{
						//	如果发现为标记则将标记数加一

						markCount += 1;
					}
					else if (blockData[x][y].isCovered)
					{
						//	其次如果未被打开则将其添加到开启列表

						uncoverList.append({ x, y });
					}
				}
			}
		}
		if (markCount == numberList[i].value)
		{
			//	如果标记数等于该处数字的值，则说明剩下的位置均不是地雷，可以安全打开

			for (int j = 0; j < uncoverList.size(); j++)
			{
				leftClick({ uncoverList[j].x, uncoverList[j].y });
			}
		}
		uncoverList.clear();
	}
}

bool MineSweeperAI::isUncertain(Point pos)
{
	//	判断一个位置是否属于不确定的位置

	if (blockData[pos.x][pos.y].isCovered && !blockData[pos.x][pos.y].isMarked)
	{
		//	首先需要该位置没有被打开和没有被标记

		for (int sideX = -1; sideX <= 1; sideX++)
		{
			for (int sideY = -1; sideY <= 1; sideY++)
			{
				int x = pos.x + sideX;
				int y = pos.y + sideY;

				if (x >= 0 && x < tableRows && y >= 0 && y < tableCols && !blockData[x][y].isCovered && blockData[x][y].number != 0)
				{
					//	其次需要在该位置的附近存在有已被打开的数字

					return true;
				}
			}
		}
	}
	return false;
}

bool MineSweeperAI::findLinkBlock(LinkBlock &link, Point pos)
{
	//	应用深度优先搜索 (DFS) 从一个初始位置找到所有与之相互制约的位置，并将结果添加到指定的列表

	if (blockData[pos.x][pos.y].isFind)
	{
		return false;
	}
	blockData[pos.x][pos.y].isFind = true;

	link.uncertainList.append({ pos.x, pos.y, 0, 0 });

	for (int sideX = -1; sideX <= 1; sideX++)
	{
		for (int sideY = -1; sideY <= 1; sideY++)
		{
			//	寻找该位置四周的数字

			int x = pos.x + sideX;
			int y = pos.y + sideY;

			if (x >= 0 && x < tableRows && y >= 0 && y < tableCols && !blockData[x][y].isCovered && blockData[x][y].number != 0)
			{
				if (!blockData[x][y].isFind)
				{
					//	如果这个数字没有被找到过，则将其添加到列表

					link.numberList.append({ x, y, blockData[x][y].number });
					blockData[x][y].isFind = true;

					//	同时继续搜索该数字四周的不确定点

					findUncertain(link, { x, y });
				}
			}
		}
	}
	return false;
}

void MineSweeperAI::findUncertain(LinkBlock &link, Point pos)
{
	//	这个函数为搜索算法的一部分，用于搜索数字四周的不确定点

	for (int sideX = -1; sideX <= 1; sideX++)
	{
		for (int sideY = -1; sideY <= 1; sideY++)
		{
			int x = pos.x + sideX;
			int y = pos.y + sideY;

			if (x >= 0 && x < tableRows && y >= 0 && y < tableCols && isUncertain({ x, y }))
			{
				findLinkBlock(link, { x, y });
			}
		}
	}
}

void MineSweeperAI::getLinkBlockData()
{
	//	获取当前界面上所有联通块的数据

	static LinkBlock link;

	for (int x = 0; x < tableRows; x++)
	{
		for (int y = 0; y < tableCols; y++)
		{
			if (isUncertain({ x, y }) && !blockData[x][y].isFind)
			{
				//	遍历整个界面找出所有的联通块

				link.uncertainList.clear();
				link.numberList.clear();
				link.ansCount = 0;

				findLinkBlock(link, { x, y });
				linkList.append(link);
			}
		}
	}
}

void MineSweeperAI::removeInvalidLink()
{
	//	去掉一些不需要进行分析的联通块

	for (int i = 0; i < linkList.size(); i++)
	{
		if (linkList[i].uncertainList.size() > LINKBLOCK_SIZE_LIMIT || linkList[i].numberList.size() == 1)
		{
			//	排除过大或只有一个数字的联通块

			linkList.erase(linkList.begin() + i--);
		}
	}
}

bool MineSweeperAI::isImpossible(unsigned long long answer)
{
	int mineCount = 0;

	while (answer)
	{
		mineCount += 1;
		answer = (answer & (answer - 1));
	}
	if (mineCount > mineLastCount)
	{
		return true;
	}
	return false;
}

void MineSweeperAI::resetAnswer()
{
	//	将判断过后所有不确定的位置上的标记还原

	for (int i = 0; i < linkList.size(); i++)
	{
		for (int j = 0; j < linkList[i].uncertainList.size(); j++)
		{
			int x = linkList[i].uncertainList[j].x;
			int y = linkList[i].uncertainList[j].y;

			blockData[x][y].isMarked = false;
		}
	}
}

void MineSweeperAI::setAnswer(LinkBlock &link, unsigned long long answer)
{
	//	按照解的方案在界面数据中设置标记

	for (int i = 0; i < link.uncertainList.size(); i++)
	{
		int x = link.uncertainList[i].x;
		int y = link.uncertainList[i].y;

		//	通过算数右移和按位与的方式将结果中第 i 位的比特取出作为是否需要标记的依据

		if (((answer >> i) & 1) == 0)
		{
			blockData[x][y].isMarked = false;
		}
		else { blockData[x][y].isMarked = true; }
	}
}

bool MineSweeperAI::isRightAnswer(LinkBlock &link)
{
	//	检查当前所设置的解决方案是否正确

	for (int i = 0; i < link.numberList.size(); i++)
	{
		//	遍历该联通块中所有的数字

		int markCount = 0;

		for (int sideX = -1; sideX <= 1; sideX++)
		{
			for (int sideY = -1; sideY <= 1; sideY++)
			{
				//	找出该数字附近的标记数量

				int x = link.numberList[i].x + sideX;
				int y = link.numberList[i].y + sideY;

				if (x >= 0 && x < tableRows && y >= 0 && y < tableCols && blockData[x][y].isCovered && blockData[x][y].isMarked)
				{
					markCount += 1;
				}
			}
		}
		if (markCount != link.numberList[i].value)
		{
			//	如果存在标记数不等于数字的数值，则此方案不成立

			return false;
		}
	}
	return true;
}

void MineSweeperAI::addAnswerCount(LinkBlock &link)
{
	//	按照解决方案，将相应位置出现地雷的次数加一

	for (int i = 0; i < link.uncertainList.size(); i++)
	{
		int x = link.uncertainList[i].x;
		int y = link.uncertainList[i].y;

		if (blockData[x][y].isMarked)
		{
			link.uncertainList[i].mineTimes += 1;
		}
	}
	link.ansCount += 1;
}

void MineSweeperAI::getProbability(LinkBlock &link)
{
	//	计算每个位置是地雷的概率

	for (int i = 0; i < link.uncertainList.size(); i++)
	{
		link.uncertainList[i].probability = (double)link.uncertainList[i].mineTimes / (double)link.ansCount;
	}
}

void MineSweeperAI::findAnswer()
{
	//	遍历所有的联通块，寻找解决方案

	for (int i = 0; i < linkList.size(); i++)
	{
		//	可能的解的个数为 2^n

		unsigned long long ansMax = pow(2, linkList[i].uncertainList.size());

		for (unsigned long long ans = 0; ans < ansMax; ans++)
		{
			// 循环变量 ans 中的每一位即解决方案的信息，0 代表不是地雷，1 代表是地雷

			if (isImpossible(ans)) { continue; }

			setAnswer(linkList[i], ans);

			if (isRightAnswer(linkList[i]))
			{
				//	如果为正确解则增加解的个数

				addAnswerCount(linkList[i]);
			}
		}
		getProbability(linkList[i]);
	}
	resetAnswer();
}

void MineSweeperAI::setResult()
{
	//	执行概率计算的结果

	QVector <Point> bestPoint;

	double probabilityMin = 1;
	bool ifHaveSure = false;
	bool ifHaveGuess = false;

	for (int i = 0; i < linkList.size(); i++)
	{
		for (int j = 0; j < linkList[i].uncertainList.size(); j++)
		{
			//	遍历所有的联通块

			int x = linkList[i].uncertainList[j].x;
			int y = linkList[i].uncertainList[j].y;

			if (linkList[i].uncertainList[j].probability == 0)
			{
				//	如果某个位置是地雷的概率为 0，则该位置不可能存在地雷，可以安全打开

				leftClick({ x, y });
				ifHaveSure = true;
			}
			else if (linkList[i].uncertainList[j].probability < probabilityMin)
			{
				//	如果概率不为 0，则寻找是地雷概率最小的位置

				probabilityMin = linkList[i].uncertainList[j].probability;
				bestPoint.clear();
				bestPoint.append({ x, y });
				ifHaveGuess = true;
			}
			else if (linkList[i].uncertainList[j].probability == probabilityMin)
			{
				bestPoint.append({ x, y });
			}
		}
	}
	if (!ifHaveSure && ifHaveGuess)
	{
		//	如果没有确定的位置但有可以猜测的位置，则判断猜测和随机哪个概率更小

		if (probabilityMin <= (double)mineLastCount / unknownCount)
		{
			//	如果概率相同则选择周围数字最少的位置

			int numberCountMin = INT_MAX;
			int bestIndex = 0;

			for (int i = 0; i < bestPoint.size(); i++)
			{
				int numberCount = 0;

				for (int sideX = -1; sideX <= 1; sideX++)
				{
					for (int sideY = -1; sideY <= 1; sideY++)
					{
						int x = bestPoint[i].x + sideX;
						int y = bestPoint[i].y + sideY;

						if (x >= 0 && x < tableRows && y >= 0 && y < tableCols && !blockData[x][y].isCovered && blockData[x][y].number != 0)
						{
							numberCount += blockData[x][y].number;
						}
					}
				}
				if (numberCount < numberCountMin)
				{
					numberCountMin = numberCount;
					bestIndex = i;
				}
			}
			leftClick(bestPoint[bestIndex]);
		}
	}
}
